package leetcode;

import java.util.HashMap;

/**
 * 题目：斐波纳契数列
 * 链接：https://leetcode.cn/problems/fibonacci-number/description/
 */
public class Fib {
    static HashMap<Integer, Integer> fibMap = new HashMap<>();
    public static void main(String[] args) {
        int fib1 = 10;
        System.out.println(fib1(fib1));
    }
    public static int fib1(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        return fib1(n - 1) + fib1(n - 2);
    }

    public static int fib2(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        if (fibMap.containsKey(n)) {
            return fibMap.get(n);
        } else {
            fibMap.put(n, fib2(n));
        }
        return fib2(n - 1) + fib2(n - 2);
    }
}
